#include <iostream>
#include "../head/TreeNode.h"
#include <cassert>

using namespace std;


// 235. Lowest Common Ancestor of a Binary Search Tree
class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		assert(p != NULL && q != NULL);

        if(root == NULL)
            return NULL;
		// pq都小于根节点在左子树
        if(p->val < root->val && q->val < root->val)
            return lowestCommonAncestor(root->left, p, q);
        if(p->val > root->val && q->val > root->val)
            return lowestCommonAncestor(root->right, p, q);
		
		// pq 一个小于node,一个大于node node 就是公共祖先
		// pq 其中一个是另一个的祖先
        assert(p->val == root->val || q->val == root->val
                || (root->val - p->val) * (root->val - q->val) < 0);

        return root;	
    }
};
